package J20250121_Dynamic;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划34——38
 * User: 王圆豪
 * Date: 2025-01-24
 * Time: 23:33
 */
public class Solution4 {
    //回文串分割Ⅱ——https://leetcode.cn/problems/palindrome-partitioning-ii/
    public int minCut(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = i+1<j ? dp[i+1][j-1] : true;
                }
            }
        }
        int[] dp1 = new int[n];
        for(int i = 0; i < n; i++) dp1[i] = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            if(dp[0][i]) dp1[i] = 0;
            else{
                for(int j = 1; j <= i; j++){
                    if(dp[j][i]){
                        dp1[i] = Math.min(dp1[i], dp1[j-1]+1);
                    }
                }
            }
        }
        return dp1[n-1];
    }
    //回文串分割Ⅳ——https://leetcode.cn/problems/palindrome-partitioning-iv/
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j<n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = i+1<j ? dp[i+1][j-1] : true;
                }
            }
        }
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n-1; j++){
                if(dp[0][i] && dp[i+1][j] && dp[j+1][n-1]){
                    return true;
                }
            }
        }
        return false;
    }

    //最长回文子串——https://leetcode.cn/problems/longest-palindromic-substring/
    public String longestPalindrome(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        int ret = 0;
        String s1 = null;
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(i+1==j){
                        dp[i][j] = 2;
                    }else if(i == j){
                        dp[i][j] = 1;
                    }else if(i+1<j && dp[i+1][j-1] != 0) {
                        dp[i][j] = dp[i+1][j-1] + 2;
                    }
                    if(ret < dp[i][j]){
                        ret = dp[i][j];
                        s1 = s.substring(i,j+1);
                    }
                }
            }
        }
        return s1;
    }

    //回文子串——https://leetcode.cn/problems/palindromic-substrings/
    public int countSubstrings(String s) {
        int m = s.length();
        boolean[][] dp = new boolean[m][m];
        int ret = 0;
        for(int i = m-1; i >= 0; i--){
            for(int j = i; j < m; j++){
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = i+1<j ? dp[i+1][j-1] : true;
                if(dp[i][j]) ret++;
            }
        }
        return ret;
    }

    //等差数列划分——https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/
    public int numberOfArithmeticSlices(int[] nums) {
        int m = nums.length;
        int[][] dp = new int[m][m];
        Map<Long, List<Integer>> map = new HashMap<>();
        map.put((long)nums[0], new ArrayList<>());
        map.get((long)nums[0]).add(0);
        int ret = 0;
        for(int i = 1; i < m; i++){
            for(int j = i + 1; j < m; j++){
                long k = (long)((long)2*nums[i] - (long)nums[j]);
                if(map.containsKey(k)){
                    List<Integer> pos = map.get(k);
                    for(int a : pos){
                        dp[i][j] += dp[a][i] + 1;
                    }
                    ret += dp[i][j];
                }
            }
            if(map.containsKey((long)nums[i])){
                map.get((long)nums[i]).add(i);
            }else{
                map.put((long)nums[i], new ArrayList<>());
                map.get((long)nums[i]).add(i);
            }
        }
        return ret;
    }
}
